{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "de0f20fb",
   "metadata": {},
   "source": [
    "# 第 2 章  行列式与矩阵的秩\n",
    "\n",
    "本章的重点是掌握行列式的计算和矩阵秩的概念.\n",
    "\n",
    "## 2.1 $n$-排列\n",
    "\n",
    "首先明确, 我们考虑的 **$n$-排列** 如果不加说明, 专指 $1, 2, \\cdots, n$ 这 $n$ 个自然数所构成的排列. 我们知道, 其全排列是 $n!$. 考虑到这 $n$ 个数是有自然顺序(从小到大)的. 因此对其任意一个排列 $i_1, i_2, \\cdots, i_n$ 中的一对数 $i_k$ 和 $i_l$, 这里 $1 \\leq k < \\leq n$, 如果 $i_k > i_l$(相当于和自然序反了), 称构成一个 $n$-排列中的**逆序(对)**. \n",
    "\n",
    "对一个任意的 $n$-排列 $i_1, i_2, \\cdots, i_n$, 其逆序对的总数如何计算? 考虑其中任意一个 $i_j$, $1 \\leq j \\leq n$, 凡是排在它之后, 但比它小的数, 都和它构成一个逆序对. 我们将这个数记为 $\\tau(i_j)$. 如此, 我们可以将这个 $n$-排列的总逆序对的个数称为**逆序数**, 记为 $\\tau(i_1 i_2 \\cdots i_n)$, 且显然有\n",
    "$$\n",
    "\\tau(i_1 i_2 \\cdots i_n) = \\sum_{j = 1}^n \\tau(i_j).\n",
    "$$\n",
    "特别地,\n",
    "$$\n",
    "\\tau(1 2 \\cdots n) = 0.\n",
    "$$\n",
    "提示: 如果一个符号的定义没有搞清楚, 那么从这个符号起, 课程内容就和你无关了. 因为每一个数学符号都有丰富的含义."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db0f673c",
   "metadata": {},
   "source": [
    "在一个 $n$-排列中, 交换两个(互异)的数的位置, 保持其它数位置不动, 称一次**对换**. 如何理解课本定理 1 的证明? 它第一步说明, 如果两个对换的数是紧挨着的, 那么对换后改变奇偶性(结论成立)；而对两个数不紧挨着的情形, 由于一共只有有限个数的排列, 我们可以从小的数开始, 用一系列紧挨着的数的对换, **等价完成**两个数的对换. 然后计算相邻数对换的总数, 即可以得到最终的结论. 这个定理的证明, 首先本质上是一个归纳过程；其次, 它是现实可以操作, 也很直观. \n",
    "\n",
    "提示: 一个定理的证明过程, 除了显示这个定理的结论在逻辑上的自洽以外, 很重要的目的是可以加强对这个结论的直观理解. 而构造性的证明, 更是包含了实际操作和演算的精髓在内. \n",
    "\n",
    "提示: 务必正确理解上述内容, 否则接下去的内容将是你一生之敌!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9518e03f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f631bf6",
   "metadata": {},
   "source": [
    "我们先做个游戏. 计算一下一个 $1, 2, 3, \\cdots, n$ 的一个排列的逆序数. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "10835937",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tau(v):\n",
    "    n = len(v)\n",
    "    tv = 0\n",
    "    for i in range(n - 1):\n",
    "        ti = 0\n",
    "        for j in range(i + 1, n):\n",
    "            if (v[j] < v[i]):\n",
    "                ti += 1\n",
    "        tv += ti\n",
    "    return tv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ffd1d937",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [1,3,5,7,8,6,4,2]\n",
    "tau(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "516b79ad",
   "metadata": {},
   "source": [
    "## 2.2 方阵的行列式\n",
    "\n",
    "我们首先指出一点, 方阵的行列式, 特别是高阶情形, 它是一个理论分析的工具而不是计算的工具. 因为从定义我们可以看到, 它要求对 $1 2 \\cdots n$ 的全排列做累加, 这是一个天文数字. 它的实际可手算上限几乎就是 $3$ 阶. \n",
    "\n",
    "提示: $4$ 阶行列式是几项求和? \n",
    "\n",
    "提示: 例 4 演示了如何直接使用行列式定义解题. 这里的思路是非常重要的.\n",
    "\n",
    "定理 2 实际上延拓了行列式的定义形式. 由它可以直接导出下一节的性质 1.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6633c188",
   "metadata": {},
   "source": [
    "## 2.3 行列式的性质\n",
    "\n",
    "因此对于求更高阶或一般的 $n$ 阶行列式, 我们需要利用矩阵的特殊结构和行列式的性质. 比如上下三角矩阵的行列式. 以及课本上的性质 1 - 6. 注意性质 2 和 6, 应该配合初等变换使用. 也就是我们一边做初等变换, 一边考虑变换下矩阵行列式的变化. 用初等变换将矩阵三角化(一般上三角), 然后得到最终结论. 这里要注意交换会变号. 详见例 5. 提示: 例 5 的变换方式不唯一, 换一种途径试试? \n",
    "\n",
    "这些性质要灵活使用, 比如:\n",
    "\n",
    "性质 3 的一个推论是如果一行或一列都是零, 那么行列式为零; \n",
    "性质 4, 要注意到它的一个特例是如果有两行(两列)元素全部相同, 那么该行列式为零; \n",
    "性质 5, 它一般要和其他性质结合使用, 比如例 6, 除了性质 5, 后几步重复使用了性质 3 做消去. \n",
    "\n",
    "要熟悉以上性质, 唯一的办法是多加练习."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21922cf5",
   "metadata": {},
   "source": [
    "## Laplace 定理\n",
    "\n",
    "这一节首先要正确理解一些概念, 要注意理解细节, 比如对 **$k$ 阶子式**的理解要注意:\n",
    "1. 原矩阵未必是方阵; \n",
    "2. 子式作用的矩阵必定是方阵;\n",
    "3. 子式作用的矩阵的指标升序, 但不一定连续; \n",
    "4. 子式本身是行列式, 而不是矩阵.\n",
    "\n",
    "对 $n$ 阶方阵 $A$ 中具体元素 $a_{ij}$ **余子式**, 首先它也是一个行列式, 而对应的矩阵是指 $a_{ij}$ 的\"补阵\", 也就是去掉了 $i$ 行和 $j$ 列全部元素之后形成的 $n - 1$ 阶矩阵. 而**代数余子式**, 则是在余子式的基础上再加上符号 $(-1)^{i + j}$, 一般记为 $A_{ij}$.\n",
    "\n",
    "以上这些定义, 务必推敲每个细节, 不可遗漏. 我们的课本, 非常浓缩, 符合数学书籍的特点, 看的时候不能太快, 要慢慢阅读, 慢慢理解. \n",
    "\n",
    "提示: 一个 $n$ 阶矩阵, 有多少个余子式? \n",
    "\n",
    "下面这个函数计算的是余矩阵(未求行列式), 供参考."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "506354ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "def comp_mat(A, i, j):\n",
    "    n = len(A)\n",
    "    I = np.r_[0:i, i + 1:n]\n",
    "    J = np.r_[0:j, j + 1:n]\n",
    "    cA = A[I][:, J]\n",
    "    return cA"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6e55e41",
   "metadata": {},
   "source": [
    "验证一下例 7 的第 2 步:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "edbdbab4",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([[7, 0, 1, 4], [1, 0, 1, 2], [3, -1, -1, 0], [7, 0, -2, -5]])\n",
    "print(\"A = \\n\", A, \"\\ndet(A) =\", np.linalg.det(A))\n",
    "Aij = comp_mat(A, 2, 1)\n",
    "print(\"Aij = \\n\", Aij, \"\\n-1 * -1**(2 + 1) * det(Aij)=\", \n",
    "      np.linalg.det(Aij) * -1 **(2 + 1) * -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "098b6284",
   "metadata": {},
   "source": [
    "定理 3 的证明思路是先选定 $i = 1$, 也即第一行, 证明结论. 然后对一般行, 通过行列式性质证明. 中间用了性质 5 作为过渡. 这个证明本身也有一定的技巧性. 而 (2.4.3) 可以看作一个推广的结论. 这些结论可以用于实际的行列式求解. 比如例 7. 其思路是将一行或一列, 通过初等变换弄出尽可能多的零, 理想情况是一行或一列中除一个元素外, 全部是零. 这样直接使用定理 3 就可以将行列式降一阶. 一般 $5$ 或 $4$ 阶行列式都需要这样处理. 这么做一般比消去到三角矩阵, 更加迅速和方便. 但这些计算都较容易出错, 需要耐心, 细致和熟练. \n",
    "\n",
    "提示: 可以看一下 $3$ 阶到 $2$ 阶的特例. \n",
    "\n",
    "例 7 是一个很有意思的特例. **Vandermonde 行列式** 是一种有实际意义的构型. 需要掌握. 课本上的证明也可以整理成数学归纳法的形式. \n",
    "\n",
    "如例 7 - 例 9 这样的 $n$ 阶行列式的计算, 需要一定的恒等变换技巧, 要反复练习. \n",
    "\n",
    "注意例 9 中出现的系数矩阵行列式, 在例 10 中有应用. **Cramer** 法则是一个理论工具, 只有在矩阵阶数很低 ($2$ 或 $3$) 才可以用于实际计算. 它的真正用途是在一些公式的推演. 下面程序提供了对 Cramer 法则的验证."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "45261ffd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Cramer_mat(A, b, i):\n",
    "    n = len(A)\n",
    "    Ai = np.hstack((A[:, np.r_[0:i]], b, A[:,np.r_[i + 1:n]]))\n",
    "    return Ai"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e5eecfc",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = np.array([[1, 2, -1, 3], [2, -1, 3, -2], [0, 3, -1, 1], [1, -1, 1, 4]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf3870c0",
   "metadata": {},
   "outputs": [],
   "source": [
    "b = np.array([[2],[7],[6],[-4]])\n",
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a538f64a",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.linalg.solve(A, b)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15598a04",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(len(A)):\n",
    "    x = np.linalg.det(Cramer_mat(A, b, i)) / np.linalg.det(A)\n",
    "    print(\"x%d = %f\\n\"%(i,x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e692867",
   "metadata": {},
   "source": [
    "**注意咱们这门课并不是数值代数, 所有的程序都只是为了明确计算规则, 而不能直接用于数值求解工作. 真正用于数值求解的程序, 还要额外考虑效率和舍入误差带来的影响, 需要修习专门的相关课程. 这一点务必请大家明确.**\n",
    "\n",
    "例 10 的证明的第一部分, 证明了形如 (2.4.5) 确实是方程 (2.4.4) 的解. 而第二部分, 则证明了所有 (2.4.4) 的解都和 (2.4.5) 相等(等价). 这是一种常见的证明途径. 值得大家参照学习.\n",
    "\n",
    "关于 **$k$ 阶子式, 余子式和代数余子式**, 要明确:\n",
    "1. 它们三者的各自含义;\n",
    "2. 子式是\"子矩阵的行列式\"的意义. 子式和余子式都是子式. 只是在矩阵上存在互补关系; 代数余子式, 表明增加了符号.\n",
    "\n",
    "而 **Laplace 定理**, 是定理 3 的推广. 这里强调一下, 子式, 余子式等等都是行列式. 行列式是数而非矩阵. 这个大家不要迷失在复杂公式中. 例 11 是一个有趣的 Laplace 定理的应用. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51cc9659",
   "metadata": {},
   "source": [
    "## 矩阵的秩\n",
    "\n",
    "我们由矩阵的非零子式的最高阶数引入**矩阵的秩**的概念, 显得非常的技术. 但是, 这不妨碍我们思考:\n",
    "1. 矩阵实际上是什么?\n",
    "2. 在我们当下, 如何直观理解矩阵的秩.\n",
    "\n",
    "在我们目前的内容中, 矩阵只是一个书写方式. 它记录了线性方程组的全部系数. 仅此而已. 我们对矩阵的操作, 如初等变换, 也是建立在线性方程组同解的意义下的. 到这里为止, 矩阵甚至不是必须的! 要说它某种程度上降低了我们演算时的书写量, 那也功能有限. 而行列式的引入, 更是将这一切沦为了数字游戏. 似乎就是一种高级的数独游戏. 然而这里定理 6 的结论却是本质的, 它指出, 从这个游戏一样的定义引出的矩阵秩, 确是初等变换中的不变量. 结合我们目前矩阵记号的背景, 线性方程组的系数, 那么秩的实际意义就指向了:\n",
    "1. 同解方程组的不变量;\n",
    "2. 一个实际的线性方程组中, 本质上的独立方程(或独立自变量)有几个?\n",
    "\n",
    "而秩是上述问题的关键. 例如:\n",
    "$$\n",
    "\\begin{array}{rcl}\n",
    "x_1 + x_2 &=& 3 \\\\\n",
    "2 x_1 + 2 x_2 &=& 6\n",
    "\\end{array}\n",
    "$$\n",
    "这里大家一眼就看出, 事实上, 我们只有一组约束(方程). 这两个方程描述的约束实质上是一样的. 或者说, $x_1$ 和 $x_2$ 这两个自变量, 本质上只有一个 $t = x_1 + x_2$. 而这一点反映在系数矩阵\n",
    "$$\n",
    "\\left(\n",
    "\\begin{array}{cc}\n",
    "1 & 1 \\\\\n",
    "2 & 2 \n",
    "\\end{array}\n",
    "\\right)\n",
    "$$\n",
    "的秩中, 它的秩是 $1$ (而不是 $2$). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc9e6554",
   "metadata": {},
   "source": [
    "## Gauss 消元过程中的不变量\n",
    "\n",
    "定理 7 实际上给出了求矩阵秩的算法: Gauss 消去成三角型(阶梯型)矩阵. 而如果我们将秩理解为独立约束的个数, 那么我们对定理 8 的结论也就不难理解. 如果增广矩阵增加了秩, 那么也意味着左边的系数矩阵提供的独立未知量数(方程数), 小于右端项提供的约束个数. 因此必然会在消元后出现 $0 = b$ 这样的\"阶梯头\", 导致无解. \n",
    "\n",
    "这里顺便指出, 这里的\"无解\"的一个必要条件是系数矩阵的秩出现\"亏损\", 也即如果系数矩阵是 $n$ 阶方阵, 那么秩 $r < n$. 因为考虑到方程总数也只有 $n$ 行, 所以增广矩阵的秩不可能大于 $n$. 也即在上面的例子中, 将右端的 $3$ 或 $6$ 改掉一个数, 方程就无解了.\n",
    "\n",
    "所以系数矩阵和增广矩阵的秩, 成为方程解的存在性的重要特征. 请结合例 13 考察这一点.\n",
    "\n",
    "同样对**方阵**(对应什么线性方程组?), 我们有**满秩**的概念来和\"秩亏损\"相对. 它是线性方程组(方阵)存在唯一解的充要条件.\n",
    "\n",
    "## 矩阵相抵\n",
    "\n",
    "在之前讨论的基础上, 以定理 9 为引, 最后得到定理 10 就是自然的: 矩阵存在\"最简形式\". 或者说, 我们能够严格地定义, 什么叫两个矩阵是**等价的**. 这个等价是在线性变换下, 它的意义是, 如果作为线性方程组的系数矩阵和增广矩阵, 它不改变解. 我们以后会看到, 随着矩阵应用的推广, 这种等价性会有更重要的意义和应用. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "914f1823",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
